package sortutil

func MergeSort(arr []int) {
	if arr == nil || len(arr) < 2 {
		return
	}
	mergeSort(arr, 0, len(arr)-1)
}

func mergeSort(arr []int, L, R int) {
	if L < R {
		mid := (L + R) / 2
		mergeSort(arr, L, mid)
		mergeSort(arr, mid+1, R)
		merge(arr, L, mid, R)
	}
}

func merge(arr []int, L, mid, R int) {
	help := make([]int, R-L+1, R-L+1)
	index := 0
	i, j := L, mid+1
	for i <= mid && j <= R {
		if arr[i] <= arr[j] {
			help[index] = arr[i]
			index++
			i++
		} else {
			help[index] = arr[j]
			index++
			j++
		}
	}
	for i <= mid {
		help[index] = arr[i]
		index++
		i++
	}
	for j <= R {
		help[index] = arr[j]
		index++
		j++
	}
	for i := 0; i < len(help); i++ {
		arr[L+i] = help[i]
	}
}
